// 474. 一和零
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
  const len = strs.length
  const dp = new Array(len + 1).fill(0).map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)))
  const cntHelper = (str) => {
    return str.split('').reduce((res, cur) => {
      if (cur === '0') {
        res[0]++
      } else if (cur === '1') {
        res[1]++
      }

      return res
    }, [0, 0])
  }

  for (let i = 1; i <= len; i++) {
    const [zeros, ones] = cntHelper(strs[i - 1])
    for (let j = 0; j <= m; j++) {
      for (let k = 0; k <= n; k++) {
        let p0 = dp[i - 1][j][k]
        let p1 = 0
        if (zeros <= j && ones <= k) {
          p1 = dp[i - 1][j - zeros][k - ones] + 1
        }

        dp[i][j][k] = Math.max(p0, p1)
      }
    }
  }

  return dp[len][m][n]
}

console.log(
  findMaxForm(
    ["10", "0001", "111001", "1", "0"],  5,  3
  )
)
